ARC074 D - 3N Numbers - 競プロ

ARC074 D - 3N Numbers

https://atcoder.jp/contests/arc074/tasks/arc074_b

提出

code: python

n = int(input())

a = list(map(int, input().split()))

a_sum = [a0]

for i in range(1, len(a)):

a_sum.append(a_sum-1 + ai)

print(a_sum)

解答

code: python

import heapq

n = int(input())

a = list(map(int, input().split()))

# 3, 1, 4, 1, 5, 9

former, latter = a:n, [-1 * i for i in a2*n:]

# print(former, latter)

sum_former, sum_latter = sum(former), sum(latter)

results = 0 * (n+1)

results0 = sum_former

resultsn = sum_latter

heapq.heapify(former)

heapq.heapify(latter)

for i in range(n, 2*n):

v = ai

p = heapq.heappushpop(former, v)

sum_former += v - p

resultsi-n+1 += sum_former

for i in range(2*n-1, n-1, -1):

v = -1 * ai

p = heapq.heappushpop(latter, v)

sum_latter += v - p

resultsi-n += sum_latter

print(max(results))

code: python

import heapq

n = int(input())

a = list(map(int, input().split()))

# print(a)

# 3, 1, 4, 1, 5, 9

# 左から left 個のところで分割して

# (左 left 個のうち大きい順に n 個の和) - (右 n-left 個のうち小さい順に n 個の和)

# を求める作業を left = n,n+1,…,2n について行ってその最大値を求める

# si := 左 i 個分の大きい順に n 個の総和

s = 0 * (n * 2 + 1)

# 前処理

que1 = []

for i in range(n):

si + 1 = si + ai

heapq.heappush(que1, ai)

# print(s)

# 0, 3, 4, 0, 0

# print(que1)

# i = 2, 3

for i in range(n, n * 2):

mina = que10

if ai > mina:

si + 1 = si - mina + ai

heapq.heappushpop(que1, ai)

else:

# print(s)

# 0, 3, 4, 7, 7

# ti := 右 i 個分の小さい順に n 個の総和

t = 0 * (n * 2 + 1)

que2 = []

for i in range(n):

ti + 1 = ti + an * 3 - 1 - i

heapq.heappush(que2, -an * 3 - 1 - i)

# print(t)

# 0, 9, 14, 0, 0

# print(que2)

# i = 2, 3

for i in range(n, n * 2):

maxa = -que20

if an * 3 - 1 - i < maxa:

ti + 1 = ti - maxa + an * 3 - 1 - i

heapq.heappushpop(que2, -an * 3 - 1 - i)

else:

# print(t)

# 0, 9, 14, 6, 5

# 集計

res = -pow(10, 10000)

# i = 2, 3, 4

for i in range(n, n * 2 + 1):

# print(i, n * 3 - i)

# 2 4

# 3 3

# 4 2

res = max(res, si - tn * 3 - i)

print(res)

テーマ

蟻本 2-4 Expedition

メモ

ABC 062 D：3N Numbers

AtCoder ABC 062 D - 3N Numbers (ARC 074 D) (青色, 500 点)

解答

code: python

n = int(input())

a = list(map(int, input().split()))

# print(a)

# 3, 1, 4, 1, 5, 9

# 全探索: O(pow(2, 1000))

# 最初から分割する意味はない

# a1 = a:len(a) // 2

# a2 = alen(a) // 2:

# a1.sort()

# a2.sort()

# print(a1)

# print(a2)